package lfu

/**
https://leetcode.cn/problems/lfu-cache/
lfu算法
策略：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。


*/

type DBNode struct {
	Cnt    int
	Key    int
	Val    int
	Front  *DBNode
	Behind *DBNode
}

type LFUCache struct {
	Capacity int
	MinCnt   int
	ValMap   map[int]*DBNode
	CountMap map[int]*LinkList
}

type LinkList struct {
	Length int
	Head   *DBNode
	Tail   *DBNode
}

func (l *LinkList) Add(node *DBNode) {
	if l.Length == 0 {
		l.Head = node
		l.Tail = node
	} else {
		l.Head.Front = node
		node.Behind = l.Head
		l.Head = node
	}
	l.Length++
}

func (l *LinkList) Pop() {
	if l.Length == 0 {
		return
	}
	if l.Length == 1 {
		l.Head = nil
		l.Tail = nil
	} else {
		old := l.Tail
		l.Tail = old.Front
		l.Tail.Behind = nil
		old.Behind = nil
	}
	l.Length--
}

func (l *LinkList) Del(node *DBNode) {
	if l.Length > 0 {
		mark := l.Head
		for mark != nil {
			if mark != node {
				mark = mark.Behind
			} else {
				if mark.Front != nil {
					mark.Front.Behind = mark.Behind
				} else {
					l.Head = mark.Behind
				}

				if mark.Behind != nil {
					mark.Behind.Front = mark.Front
				} else {
					l.Tail = mark.Behind
				}

				mark.Front = nil
				mark.Behind = nil
				l.Length--
			}
		}
	}
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		Capacity: capacity,
		ValMap:   make(map[int]*DBNode),
		CountMap: make(map[int]*LinkList),
	}
}

func (this *LFUCache) Get(key int) int {
	if res, ok := this.ValMap[key]; ok {
		this.Refresh(res)
		return res.Val
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {

	if this.Capacity == 0 {
		return
	}

	if _, ok := this.ValMap[key]; ok {
		this.ValMap[key].Val = value
		this.Refresh(this.ValMap[key])
		return
	}

	if len(this.ValMap) == this.Capacity {
		delNode := this.CountMap[this.MinCnt].Tail
		this.CountMap[this.MinCnt].Del(delNode)
		delete(this.ValMap, delNode.Key)
	} else {
		this.Capacity++
	}

	node := &DBNode{Cnt: 1, Key: key, Val: value}
	this.addNode(node)
	this.ValMap[key] = node
	this.MinCnt = node.Cnt
}

func (this *LFUCache) addNode(node *DBNode) {
	l, ok := this.CountMap[node.Cnt]
	if !ok {
		l = &LinkList{}
		this.CountMap[node.Cnt] = l
	}
	l.Add(node)
}

func (this *LFUCache) Refresh(node *DBNode) {
	this.CountMap[node.Cnt].Del(node)
	if this.CountMap[node.Cnt].Length == 0 {
		delete(this.CountMap, node.Cnt)
		if this.MinCnt == node.Cnt {
			this.MinCnt++
		}
	}

	node.Cnt++
	this.CountMap[node.Cnt].Add(node)
}
